#include "Graph.h"

UndirectedGraphPtr createUndirectedGraph(int totalVertices){
    UndirectedGraphPtr graph = malloc(sizeof(struct UndirectedGraph) + sizeof(struct adjacency *) * totalVertices);
    assert(graph);
    graph->totalVertices = totalVertices;
    graph->totalEdges = 0;
    for (int i = 0; i < totalVertices; i++) {
        graph->adjacencyList[i] = malloc(sizeof(struct adjacency));
        assert(graph->adjacencyList[i]);
        graph->adjacencyList[i]->capacity = 0;
        graph->adjacencyList[i]->length = 0;
    }
    return graph;
}

void destroyUndirectedGraph(UndirectedGraphPtr graph) {
    for (int i = 0; i < graph->totalVertices; i++) {
        free(graph->adjacencyList[i]);
    }
    free(graph);
}

void ugraphAddEdge(UndirectedGraphPtr graph, int src, int dest) {
    assert(src >= 0);
    assert(dest >= 0);
    assert(src < graph->totalVertices);
    assert(dest < graph->totalVertices);
    assert(src != dest);

    _ugraphAddEdge(graph, src, dest);
    _ugraphAddEdge(graph, dest, src);
}

void _ugraphAddEdge(UndirectedGraphPtr graph, int src, int dest) {
    if (graph->adjacencyList[src]->length == graph->adjacencyList[src]->capacity) {
        graph->adjacencyList[src]->capacity = graph->adjacencyList[src]->capacity * 2 + 1;
        graph->adjacencyList[src] = realloc(graph->adjacencyList[src],
                                            sizeof(struct adjacency)
                                                    + sizeof(int) * graph->adjacencyList[src]->capacity);
    }
    graph->adjacencyList[src]->list[graph->adjacencyList[src]->length++] = dest;
    graph->totalEdges++;
}

void printUgraphDfs(UndirectedGraphPtr graph, int vertex) {
    int visited[graph->totalVertices];
    memset(visited, 0, sizeof(visited));
    ugraphDfs(graph, visited, vertex);
}

void ugraphDfs(UndirectedGraphPtr graph, int visited[], int vertex) {
    visited[vertex] = 1;
    printf("%d -> ", vertex);
    for (int i = 0; i < graph->adjacencyList[vertex]->length; i++) {
        int adjVertex = graph->adjacencyList[vertex]->list[i];
        if (visited[adjVertex] == 0) {
            ugraphDfs(graph, visited, adjVertex);
        }
    }
}


